package alg20241219;

public class Text {
    int[] tmp;
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        merge(nums, 0, nums.length-1);
        return nums;
    }

    public void merge(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = (left + right) / 2;
        //左边区间排序
        merge(nums, left, mid);
        //右边区间排序
        merge(nums, mid + 1, right);

        //合并两个有序数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right) {
            while(cur1 <= mid && nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            while(cur2 <= right && nums[cur2] <= nums[cur1])
                tmp[i++] = nums[cur2++];

        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }
}
